package com.sunny.l36;

public class Solution {
    public int numDistinct(String S, String T) {
        if(null == S || null == T || S.length() < T.length())
            return 0;
        int[][] dp = new int[T.length()+1][S.length()+1];
        for(int i=0;i<=T.length();i++){
            dp[i][0] = 0;
        }
        for(int i=0;i<=S.length();i++){
            dp[0][i] = 1;
        }
        int startj = 1;
        boolean isFirst;
        for(int i=1;i<=T.length();i++){
            isFirst = true;
            for(int j=startj;j<=S.length();j++){
                if(T.charAt(i-1) == S.charAt(j-1)){
                    if(isFirst) {
                        isFirst = false;
                        startj = j + 1;
                        dp[i][j] = dp[i-1][j-1];
                    }else{
                        dp[i][j] = dp[i][j-1] + dp[i-1][j-1];
                    }
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        return dp[T.length()][S.length()];
    }
}
